#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;


class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */

    ListNode* sortInList(ListNode* head) {
        // write code here
        if(!head || !head->next) return head;
        vector<ListNode*> v;
        ListNode* cur = head;
        while(cur)
        {
            v.emplace_back(cur);
            cur = cur->next;
        }
        sort(v.begin(),v.end(),Cmp());
        //重新链接
        for(int i = 0;i<v.size()-1;i++)
        {
            v[i]->next = v[i+1];
        }
        //注意最后一个节点的next要置空
        v[v.size()-1]->next = nullptr;

        return v[0];
    }
};


class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */

    ListNode* sortInList(ListNode* head) {
        // write code here
        if(!head || !head->next) return head;
        vector<ListNode*> v;
        ListNode* cur = head;
        while(cur)
        {
            v.emplace_back(cur);
            cur = cur->next;
        }
        sort(v.begin(),v.end(),Cmp());
        //重新链接
        for(int i = 0;i<v.size()-1;i++)
        {
            v[i]->next = v[i+1];
        }
        //注意最后一个节点的next要置空
        v[v.size()-1]->next = nullptr;

        return v[0];
    }
};